{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python机器学习（第15期）第5课书面作业\n",
    "学号：113727  \n",
    "\n",
    "**作业：**\n",
    "1. ESL第310页第2段“The Gini index can be interpreted in two interesting ways...”  \n",
    "请用具体的计算推导过程完善这段话里对基尼指数意义的解释\n",
    "2. 这里有gcForest的“官方实现”  \n",
    "https://github.com/kingfengji/gcForest  \n",
    "请部署有关代码并跑通一个demo，抓图实验过程"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 作业1\n",
    "ESL第310页第2段“The Gini index can be interpreted in two interesting ways...”  \n",
    "请用具体的计算推导过程完善这段话里对基尼指数意义的解释"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ESL第310页第2段话如下：  \n",
    "The Gini index can be interpreted in two interesting ways. Rather than\n",
    "classify observations to the majority class in the node, we could classify\n",
    "them to class k with probability $\\hat{p}_{mk}$. Then the training error rate of this\n",
    "rule in the node is$\\sum_{k\\neq k'} \\hat{p}_{mk} \\hat{p}_{mk'}$ —the Gini index. Similarly, if we code\n",
    "each observation as 1 for class k and zero otherwise, the variance over the\n",
    "node of this 0-1 response is $\\hat{p}_{mk}(1-\\hat{p}_{mk})$. Summing over classes k again\n",
    "gives the Gini index."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "针对第一种解释：  \n",
    "假设有$K$种分类，对于分类某种分类$k$，其概率为$\\hat{p}_{mk}$，那么分错的概率就是$1-\\hat{p}_{mk}$，那么整体分错率就是：  \n",
    "$$\n",
    "\\begin{align*}\n",
    "\\sum_{k=1}^{K}\\hat{p}_{mk}(1-\\hat{p}_{mk})&=\\sum_{k=1}^{K}\\hat{p}_{mk}\\sum_{k'=1,k' \\neq k}^{K} \\hat{p}_{mk'} \\\\\n",
    "&=\\sum_{k\\neq k'} \\hat{p}_{mk} \\hat{p}_{mk'}\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "针对第二种解释，我的理解如下：  \n",
    "如果我们用二叉树来做决策树，那么节点分裂时，最多两个分叉，这个其实与书中第二种解释是对上的，如果对于观察值分类到$k$类标记为值1，其他就标记为值0，那么这个节点的方差为：  \n",
    "假设观察值有N个，分到$k$类有M个，所以$\\hat{p}_{mk}=\\frac{M}{N}$。  \n",
    "$$\n",
    "\\begin{align*}\n",
    "var(node)&=\\frac{1}{N}\\sum_{i=1}^N (x_i-c)^2 \\\\\n",
    "&=\\frac{1}{N}\\sum_{i=1}^N (x_i^2-2cx_i+c^2) \\\\\n",
    "&=\\frac{1}{N}\\sum_{i=1}^N (x_i^2)-\\frac{2}{N^2}\\sum_{i=1}^N (x_i)\\sum_{i=1}^N (x_i)+\\frac{1}{N}\\sum_{i=1}^N (x_i)\\frac{1}{N}\\sum_{i=1}^N (x_i) \\frac{1}{N} \\sum_{i=1}^{N} 1 \\\\\n",
    "&=\\frac{1}{N}\\sum_{i=1}^N (x_i^2)-\\frac{2}{N^2}\\sum_{i=1}^N (x_i)\\sum_{i=1}^N (x_i)+\\frac{1}{N^2}\\sum_{i=1}^N (x_i)\\sum_{i=1}^N (x_i) \\\\\n",
    "&=\\frac{1}{N}\\sum_{i=1}^N (x_i^2)-\\frac{1}{N^2}\\sum_{i=1}^N (x_i)\\sum_{i=1}^N (x_i) \\\\\n",
    "&=\\frac{M}{N}-\\frac{M^2}{N^2} \\\\\n",
    "&=\\frac{M}{N}(1-\\frac{M}{N}) \\\\\n",
    "&=\\hat{p}_{mk}(1-\\hat{p}_{mk})\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
